package com.yq.practice.tree;

import java.util.Arrays;

/**
 * @ClassName HeapSortPractice
 * @Description TODO
 * @Author yaoqiang
 * @Date 2021/11/17 09:19
 * @Version 1.0
 */
public class HeapSortPractice {
    public static void main(String[] args) {
        int[] arr = {5, 3, 6, 8, 7, 9};
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        int temp = 0;
        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int temp=arr[i];
        for (int k=2*i+1;k<length;k=2*k+1){
            if(k+1<length && arr[k+1]>arr[k]){
                k++;
            }
            if(arr[k]>arr[i]){
                arr[i]=arr[k];
                i=k;
            }else{
                break;
            }
        }
        arr[i]=temp;
    }



   /* 2021/11/16 15:40
       public static void main(String[] args) {
        int[] arr={3,7,6,4,5,2};
        for (int i=arr.length/2-1;i>=0;i--){
            adjustSort(arr,i,arr.length);
        }
        int temp=0;
        for (int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustSort(arr,0,j);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void adjustSort(int[] arr, int i, int length) {
        int temp=arr[i];
        for (int k=2*i+1;k<length;k=k*2+1){
            if (k+1<length&& arr[k]<arr[k+1]){
                k++;
            }
            if(arr[k]>arr[i]){
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;

    }


   public static void main(String[] args) {
        int[] arr={4,5,6,9,7};
        //循环从length/2-1的节点开始堆排序
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //调整位置，堆排整理
        int temp=0;
        for (int j=arr.length-1;j>0;j--){
            temp=arr[j];

            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }

        //输出
        System.out.println(Arrays.toString(arr));
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int temp =arr[i];
        for (int k=2*i+1;k<length;k=2*k+1){
            if(k+1<length&& arr[k]<arr[k+1]){
                k++;
            }
            if(arr[k]>arr[i]){
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;
    }

           for (int i=arr.length/2-1;i>=0;i--){
            adjustSort(arr,i,arr.length);
        }
        int temp =0;
        for (int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustSort(arr,0,j);
        }


        int temp=arr[i];
        for (int k=2*i+1;k<length;k=2*k+1){
            if (k+1<length&& arr[k]<arr[k+1]){
                k++;
            }
            if(arr[k]>arr[i]){
                arr[i]=arr[k];
                i=k;
            }else{
                break;
            }
        }
        arr[i]=temp;
  public static void main(String[] args) {
        int[] arr={4,9,8,5,6};
        //大顶堆排序，先进行堆排序，再交换数组收尾位置，继续循环（数组依次减小）
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {

        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        int temp=0;
        for (int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;

            adjustHeap(arr,0,j);
        }
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int temp=arr[i];
        for (int k=2*i+1;k<length;k=2*k+1){
            if(k+1<length&& arr[k]<arr[k+1]){
                k++;
            }
            if(arr[k]>temp){
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;
    }
    */


}
